package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/9/23 10:14
 */
public class BinarySearch {

    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = Integer.compare(nums[mid], target);
            if (cmp == 0) {
                return mid;
            } else if (cmp > 0) {
                right = mid - 1;
            } else if (cmp < 0) {
                left = mid + 1;
            }
        }
        // 没有找到
        return -1;
    }

    // 向左一定是left = mid + 1
    // 向右一定是right = mid
    public int binarySearchLeftBound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cmp = Integer.compare(nums[mid], target);
            if (cmp == 0) {
                // 唯一区别是在cmp == 0的时候，选择的收缩方式
                right = mid;
            } else if (cmp > 0) {
                right = mid;
            } else if (cmp < 0) {
                left = mid + 1;
            }
        }
        //left和right是相等的
        //又mid=right -- 收缩方式决定
        return left;
    }

    public int binarySearchRightBound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cmp = Integer.compare(nums[mid], target);
            if (cmp == 0) {
                // 只有这里不同，决定收缩方向
                left = mid + 1;
            } else if (cmp > 0) {
                right = mid;
            } else if (cmp < 0){
                left = mid + 1;
            }
        }
        // 返回的是mid的位置，mid一直是left = mid+1
        // 所以返回left - 1
        return left - 1;
    }

    static class Solution {
        public int binarySearch(int[] nums, int target) {
            int i = 0, j = nums.length - 1;
            while (i <= j) {
                int mid = i + (j - i) /2;
                int cmp = Integer.compare(nums[mid], target);
                if (cmp == 0) {
                    return mid;
                } else if (cmp > 0) {
                    j = mid - 1;
                } else if (cmp < 0) {
                    i = mid + 1;
                }
            }
            return -1;
        }

        public int binarySearchLeftBound(int[] nums, int target) {
            int i = 0, j = nums.length;
            while (i < j) {
                int mid = i + (j - i) / 2;
                int cmp = Integer.compare(nums[mid], target);
                if (cmp == 0) {
                    j = mid;
                } else if (cmp > 0) {
                    j = mid;
                } else {
                    i = mid + 1;
                }
            }
            return j;
        }

        public int binarySearchRightBound(int[] nums, int target) {
            int i = 0, j = nums.length;
            while (i < j) {
                int mid = i + (i - j) / 2;
                int cmp = Integer.compare(nums[mid], target);
                if (cmp == 0) {
                    i = mid + 1;
                } else if (cmp > 0) {
                    j = mid;
                } else if (cmp < 0){
                    i = mid + 1;
                }
            }
            return i - 1;
        }
    }



}
